package org.korifey.ffalg;

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Random;

public final class Probabilities {
	static final int MAX_COMBINATIONS = 100; 
	static long[][] combinations = new long[MAX_COMBINATIONS][];	
	static Random random = new Random();
	static {
		for (int n=0; n<MAX_COMBINATIONS; n++) {
			combinations[n] = new long[Math.max(n+1, 2)];
			combinations[n][0] = 1;
			combinations[n][n] = 1;
			combinations[n][1] = n;
		}
	}
	
	public static final long combinationsByPascalTriangle(int n, int k) {
		assert k>=0;
		assert k<=n;
		assert n <= MAX_COMBINATIONS;		
		
		if (combinations[n][k] == 0) {
			combinations[n][k] = combinationsByPascalTriangle(n-1, k-1) + combinationsByPascalTriangle(n-1, k);
		}
		return combinations[n][k];
	}
	
	static final int MAX_FACTORIALS = 20;
	static long[] factorials = new long[MAX_FACTORIALS+1];
	static {
		factorials[0] = 1;
		for (int i=1; i<=MAX_FACTORIALS; i++) factorials[i] = factorials[i-1]*i;
	}
	
	public static long factorial(int n) {
		assert n >= 0;
		assert n <= MAX_FACTORIALS;
		return factorials[n];
	}
	
	public static int[] generateRandomArray(int n, int lower, int upper) {
		int[] res = new int[n];
		Random r = new Random();
		for (int i=0; i<n; i++) res[i] = r.nextInt(upper + 1 - lower) + lower;
		return res;
	}
	
	public static int[] factRadixToPermutation(long x, int n) {
		assert x < factorials[n];
		boolean[] used = new boolean[n];
		int[] res = new int[n];
		for (int i=1; i<=n; i++) {
			int p = (int)(x / factorials[n-i]);
			for (int j = 0, cnt = 0;;j++) {
				if (!used[j]) {
					if (cnt < p) cnt++;
					else {
						res[i-1] = j;
						used[j] = true;
						break;
					}
				}
			}
			x = x - p*factorials[n-i];
		}
		return res;
	}
	
	public static  Iterator<int[]> generatePermutations(final int n) {
		assert n > 0;
		return new Iterator<int[]>() {			
			int nxtNumber = 0;
			@Override
			public boolean hasNext() {				
				return nxtNumber < factorials[n];
			}
			
			@Override
			public int[] next() {
				int p = nxtNumber++;
				return factRadixToPermutation(p, n);
			}
			
			@Override
			public void remove() {
				throw new UnsupportedOperationException();
			}
		};
	}
	
	public static Iterator<int[]> generateCombinations(final int n, final int k) {
		assert k>0;
		assert k<=n;
		return new Iterator<int[]>() {
			int[] nxt = new int[k];		
			{
				for (int i=0; i<nxt.length; i++) nxt[i] = i;
			}
			
			@Override
			public boolean hasNext() {				
				return nxt != null;
			}
					

			@Override
			public int[] next() {
				int[] ret = nxt.clone();
				if (ret.length == 0 || ret[0] == n-k) {
					nxt = null;
				} else {
					int pos = -1;
					for (int i=0; i<k-1; i++) {
						if (nxt[i] < nxt[i+1]-1) {
							pos = i;
							break;
						}
					}
					if (pos == -1) pos = k-1;
					
					for (int i=0; i<pos; i++) {
						nxt[i] = i;
					}
					nxt[pos]++;
					
				}
				return ret;
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException();
			}};
	}
}
